using System;

namespace ClearSpringNet.Stream.Cardinality
{
    /// <summary>
    /// Implementationt of HyperLogLog in C# : Author : Jeremy Woo 
    /// http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
    /// </summary>
    public class HyperLogLog
    {
        private double _stdError;
        private double m;
        private double k;
        private int k_comp;
        private double alpha_m;
        private double[] M;

        public uint MaxPower { get { return pow_2_32; } }

        private uint pow_2_32 = uint.MaxValue;

        public HyperLogLog(double stdError)
        {
            _stdError = stdError;
            InitializationVariables();
        }

        private static double Log2(double x)
        {
            return Math.Log(x, 2);
        }

        private static int Rank(int hash, int max)
        {
            var r = 1;
            while ((hash & 1) == 0 && r <= max) { ++r; hash >>= 1; }
            return r;
        }

        private void InitializationVariables()
        {
            m = 1.04 / _stdError;
            k = Math.Ceiling(Log2(m * m));
            k_comp = Convert.ToInt32(32 - k);
            m = Math.Pow(2, k);
            alpha_m = m == 16 ? 0.673 : m == 32 ? 0.697 : m == 64 ? 0.709 : 0.7213 / (1 + 1.079 / m);

            M = new double[(int)m];

            for (var i = 0; i < m; ++i)
                M[i] = 0;
        }

        public void FeedKey(int hash)
        {
            var j = (uint) hash >> k_comp;
            M[j] = Math.Max(M[j], Rank(hash, k_comp));
        }
        
        public double GetItemCount()
        {
            var c = 0.0;
            for (var i = 0; i < m; ++i) c += 1 / Math.Pow(2, M[i]);
            var E = alpha_m * m * m / c;

            if (E <= 5 / 2 * m)
            {
                var V = 0;
                for (var i = 0; i < m; ++i) if (M[i] == 0) ++V;
                if (V > 0) E = m * Math.Log(m / V);
            }
            else if (E > 1 / 30 * pow_2_32)
                E = -pow_2_32 * Math.Log(1 - E / pow_2_32);

            return E;
        }

        public static uint fnv1a(string text)
        {
            var hash = 2166136261;
            for (var i = 0; i < text.Length; ++i)
            {
                hash ^= text[i];
                hash += (hash << 1) + (hash << 4) + (hash << 7) +
                  (hash << 8) + (hash << 24);
            }
            return hash >> 0;
        }
    }
}